package com.sugon.thread;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * FormJoin排序
 */
public class ForkJoinSort {

	public static void main(String[] args) {
		Random random = new Random();
		
		int[] data = new int[5000000];
		for(int i = 0 ; i < data.length ; i++){
			data[i] = random.nextInt(5000000); 
		}


		ForkJoinPool pool = new ForkJoinPool();
		MySortTask main = new MySortTask(data , 0 , data.length);
		pool.invoke(main);

		//Arrays.parallelSort(data);

		for(int i = 0 ; i < 100 ; i++){
			System.out.println(data[i]);
		}
	}

}

/**
 * 用于无返回值的任务
 */
class MySortTask extends RecursiveAction{
	int[] data;
	/**
	 * 起始下标  包含
	 */
	int start;
	/**
	 *结束下标 不包含
	 */
	int end;
	/**
	 * 阈值
	 */
	static final int THRESHOLD = 1000;
	
	public MySortTask(int[] data, int start, int end) {
		super();
		this.data = data;
		this.start = start;
		this.end = end;
	}

	@Override
	public void compute(){
		if (end - start <= THRESHOLD){
			Arrays.sort(data , start , end);
		}
		else{
			int middle = (start+end)/2;
			MySortTask task1 = new MySortTask(data, start, middle);
			MySortTask task2 = new MySortTask(data, middle, end);
			//等线程任务执行完毕后,取得全部任务的结果值。
			invokeAll(task1 , task2);
			merge(middle);
		}
	}

	/**
	 * 将2个有序的数组 合并成有序的大数组
	 * @param middle
	 */
	private void merge(int middle){
		int[] a = Arrays.copyOfRange(data, start, middle);
		int[] b = Arrays.copyOfRange(data, middle, end);
		
		int x = 0; 
		int y = 0;
		for(int i = start ; i < end ; i++){
			if (x == a.length) data[i] = b[y++];
			else if (y == b.length) data[i] = a[x++];
			else if (a[x] < b[y]) data[i] = a[x++];
			else data[i] = b[y++];
		}
				
	}
}







